// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "cc/base/list_container_helper.h"

#include <stddef.h>

#include <algorithm>
#include <vector>

#include "base/logging.h"
#include "base/macros.h"

namespace {
const size_t kDefaultNumElementTypesToReserve = 32;
} // namespace

namespace cc {

// CharAllocator
////////////////////////////////////////////////////
// This class deals only with char* and void*. It does allocation and passing
// out raw pointers, as well as memory deallocation when being destroyed.
class ListContainerHelper::CharAllocator {
public:
    // CharAllocator::InnerList
    /////////////////////////////////////////////
    // This class holds the raw memory chunk, as well as information about its
    // size and availability.
    struct InnerList {
        std::unique_ptr<char[]> data;
        // The number of elements in total the memory can hold. The difference
        // between capacity and size is the how many more elements this list can
        // hold.
        size_t capacity;
        // The number of elements have been put into this list.
        size_t size;
        // The size of each element is in bytes. This is used to move from between
        // elements' memory locations.
        size_t step;

        InnerList()
            : capacity(0)
            , size(0)
            , step(0)
        {
        }

        void Erase(char* position)
        {
            // Confident that destructor is called by caller of this function. Since
            // CharAllocator does not handle construction after
            // allocation, it doesn't handle desctrution before deallocation.
            DCHECK_LE(position, LastElement());
            DCHECK_GE(position, Begin());
            char* start = position + step;
            std::copy(start, End(), position);

            --size;
            // Decrease capacity to avoid creating not full not last InnerList.
            --capacity;
        }

        void InsertBefore(char** position, size_t count)
        {
            DCHECK_LE(*position, LastElement() + step);
            DCHECK_GE(*position, Begin());

            // Adjust the size and capacity
            size_t old_size = size;
            size += count;
            capacity = size;

            // Allocate the new data and update the iterator's pointer.
            std::unique_ptr<char[]> new_data(new char[size * step]);
            size_t position_offset = *position - Begin();
            *position = new_data.get() + position_offset;

            // Copy the data before the inserted segment
            memcpy(new_data.get(), data.get(), position_offset);
            // Copy the data after the inserted segment.
            memcpy(new_data.get() + position_offset + count * step,
                data.get() + position_offset, old_size * step - position_offset);
            new_data.swap(data);
        }

        bool IsEmpty() const { return !size; }
        bool IsFull() { return capacity == size; }
        size_t NumElementsAvailable() const { return capacity - size; }

        void* AddElement()
        {
            DCHECK_LT(size, capacity);
            ++size;
            return LastElement();
        }

        void RemoveLast()
        {
            DCHECK(!IsEmpty());
            --size;
        }

        char* Begin() const { return data.get(); }
        char* End() const { return data.get() + size * step; }
        char* LastElement() const { return data.get() + (size - 1) * step; }
        char* ElementAt(size_t index) const { return data.get() + index * step; }

    private:
        DISALLOW_COPY_AND_ASSIGN(InnerList);
    };

    explicit CharAllocator(size_t element_size)
        : element_size_(element_size)
        , size_(0)
        , last_list_index_(0)
        , last_list_(nullptr)
    {
        AllocateNewList(kDefaultNumElementTypesToReserve);
        last_list_ = storage_[last_list_index_].get();
    }

    CharAllocator(size_t element_size, size_t element_count)
        : element_size_(element_size)
        , size_(0)
        , last_list_index_(0)
        , last_list_(nullptr)
    {
        AllocateNewList(element_count > 0 ? element_count
                                          : kDefaultNumElementTypesToReserve);
        last_list_ = storage_[last_list_index_].get();
    }

    ~CharAllocator() { }

    void* Allocate()
    {
        if (last_list_->IsFull()) {
            // Only allocate a new list if there isn't a spare one still there from
            // previous usage.
            if (last_list_index_ + 1 >= storage_.size())
                AllocateNewList(last_list_->capacity * 2);

            ++last_list_index_;
            last_list_ = storage_[last_list_index_].get();
        }

        ++size_;
        return last_list_->AddElement();
    }

    size_t element_size() const { return element_size_; }
    size_t list_count() const { return storage_.size(); }
    size_t size() const { return size_; }
    bool IsEmpty() const { return size() == 0; }

    size_t Capacity() const
    {
        size_t capacity_sum = 0;
        for (const auto& inner_list : storage_)
            capacity_sum += inner_list->capacity;
        return capacity_sum;
    }

    void Clear()
    {
        // Remove all except for the first InnerList.
        DCHECK(!storage_.empty());
        storage_.erase(storage_.begin() + 1, storage_.end());
        last_list_index_ = 0;
        last_list_ = storage_[0].get();
        last_list_->size = 0;
        size_ = 0;
    }

    void RemoveLast()
    {
        DCHECK(!IsEmpty());
        last_list_->RemoveLast();
        if (last_list_->IsEmpty() && last_list_index_ > 0) {
            --last_list_index_;
            last_list_ = storage_[last_list_index_].get();

            // If there are now two empty inner lists, free one of them.
            if (last_list_index_ + 2 < storage_.size())
                storage_.pop_back();
        }
        --size_;
    }

    void Erase(PositionInCharAllocator* position)
    {
        DCHECK_EQ(this, position->ptr_to_container);

        // Update |position| to point to the element after the erased element.
        InnerList* list = storage_[position->vector_index].get();
        char* item_iterator = position->item_iterator;
        if (item_iterator == list->LastElement())
            position->Increment();

        list->Erase(item_iterator);
        // TODO(weiliangc): Free the InnerList if it is empty.
        --size_;
    }

    void InsertBefore(ListContainerHelper::Iterator* position, size_t count)
    {
        if (!count)
            return;

        // If |position| is End(), then append |count| elements at the end. This
        // will happen to not invalidate any iterators or memory.
        if (!position->item_iterator) {
            // Set |position| to be the first inserted element.
            Allocate();
            position->vector_index = storage_.size() - 1;
            position->item_iterator = storage_[position->vector_index]->LastElement();
            // Allocate the rest.
            for (size_t i = 1; i < count; ++i)
                Allocate();
        } else {
            storage_[position->vector_index]->InsertBefore(&position->item_iterator,
                count);
            size_ += count;
        }
    }

    InnerList* InnerListById(size_t id) const
    {
        DCHECK_LT(id, storage_.size());
        return storage_[id].get();
    }

    size_t FirstInnerListId() const
    {
        // |size_| > 0 means that at least one vector in |storage_| will be
        // non-empty.
        DCHECK_GT(size_, 0u);
        size_t id = 0;
        while (storage_[id]->size == 0)
            ++id;
        return id;
    }

    size_t LastInnerListId() const
    {
        // |size_| > 0 means that at least one vector in |storage_| will be
        // non-empty.
        DCHECK_GT(size_, 0u);
        size_t id = storage_.size() - 1;
        while (storage_[id]->size == 0)
            --id;
        return id;
    }

    size_t NumAvailableElementsInLastList() const
    {
        return last_list_->NumElementsAvailable();
    }

private:
    void AllocateNewList(size_t list_size)
    {
        std::unique_ptr<InnerList> new_list(new InnerList);
        new_list->capacity = list_size;
        new_list->size = 0;
        new_list->step = element_size_;
        new_list->data.reset(new char[list_size * element_size_]);
        storage_.push_back(std::move(new_list));
    }

    std::vector<std::unique_ptr<InnerList>> storage_;
    const size_t element_size_;

    // The number of elements in the list.
    size_t size_;

    // The index of the last list to have had elements added to it, or the only
    // list if the container has not had elements added since being cleared.
    size_t last_list_index_;

    // This is equivalent to |storage_[last_list_index_]|.
    InnerList* last_list_;

    DISALLOW_COPY_AND_ASSIGN(CharAllocator);
};

// PositionInCharAllocator
//////////////////////////////////////////////////////
ListContainerHelper::PositionInCharAllocator::PositionInCharAllocator(
    const ListContainerHelper::PositionInCharAllocator& other)
    : ptr_to_container(other.ptr_to_container)
    , vector_index(other.vector_index)
    , item_iterator(other.item_iterator)
{
}

ListContainerHelper::PositionInCharAllocator::PositionInCharAllocator(
    ListContainerHelper::CharAllocator* container,
    size_t vector_ind,
    char* item_iter)
    : ptr_to_container(container)
    , vector_index(vector_ind)
    , item_iterator(item_iter)
{
}

bool ListContainerHelper::PositionInCharAllocator::operator==(
    const ListContainerHelper::PositionInCharAllocator& other) const
{
    DCHECK_EQ(ptr_to_container, other.ptr_to_container);
    return vector_index == other.vector_index && item_iterator == other.item_iterator;
}

bool ListContainerHelper::PositionInCharAllocator::operator!=(
    const ListContainerHelper::PositionInCharAllocator& other) const
{
    return !(*this == other);
}

ListContainerHelper::PositionInCharAllocator
ListContainerHelper::PositionInCharAllocator::Increment()
{
    CharAllocator::InnerList* list = ptr_to_container->InnerListById(vector_index);
    if (item_iterator == list->LastElement()) {
        ++vector_index;
        while (vector_index < ptr_to_container->list_count()) {
            if (ptr_to_container->InnerListById(vector_index)->size != 0)
                break;
            ++vector_index;
        }
        if (vector_index < ptr_to_container->list_count())
            item_iterator = ptr_to_container->InnerListById(vector_index)->Begin();
        else
            item_iterator = NULL;
    } else {
        item_iterator += list->step;
    }
    return *this;
}

ListContainerHelper::PositionInCharAllocator
ListContainerHelper::PositionInCharAllocator::ReverseIncrement()
{
    CharAllocator::InnerList* list = ptr_to_container->InnerListById(vector_index);
    if (item_iterator == list->Begin()) {
        --vector_index;
        // Since |vector_index| is unsigned, we compare < list_count() instead of
        // comparing >= 0, as the variable will wrap around when it goes out of
        // range (below 0).
        while (vector_index < ptr_to_container->list_count()) {
            if (ptr_to_container->InnerListById(vector_index)->size != 0)
                break;
            --vector_index;
        }
        if (vector_index < ptr_to_container->list_count()) {
            item_iterator = ptr_to_container->InnerListById(vector_index)->LastElement();
        } else {
            item_iterator = NULL;
        }
    } else {
        item_iterator -= list->step;
    }
    return *this;
}

// ListContainerHelper
////////////////////////////////////////////
ListContainerHelper::ListContainerHelper(size_t max_size_for_derived_class)
    : data_(new CharAllocator(max_size_for_derived_class))
{
}

ListContainerHelper::ListContainerHelper(size_t max_size_for_derived_class,
    size_t num_of_elements_to_reserve_for)
    : data_(new CharAllocator(max_size_for_derived_class,
        num_of_elements_to_reserve_for))
{
}

ListContainerHelper::~ListContainerHelper() { }

void ListContainerHelper::RemoveLast()
{
    data_->RemoveLast();
}

void ListContainerHelper::EraseAndInvalidateAllPointers(
    ListContainerHelper::Iterator* position)
{
    data_->Erase(position);
}

void ListContainerHelper::InsertBeforeAndInvalidateAllPointers(
    ListContainerHelper::Iterator* position,
    size_t count)
{
    data_->InsertBefore(position, count);
}

ListContainerHelper::ConstReverseIterator ListContainerHelper::crbegin() const
{
    if (data_->IsEmpty())
        return crend();

    size_t id = data_->LastInnerListId();
    return ConstReverseIterator(data_.get(), id,
        data_->InnerListById(id)->LastElement(), 0);
}

ListContainerHelper::ConstReverseIterator ListContainerHelper::crend() const
{
    return ConstReverseIterator(data_.get(), static_cast<size_t>(-1), NULL,
        size());
}

ListContainerHelper::ReverseIterator ListContainerHelper::rbegin()
{
    if (data_->IsEmpty())
        return rend();

    size_t id = data_->LastInnerListId();
    return ReverseIterator(data_.get(), id,
        data_->InnerListById(id)->LastElement(), 0);
}

ListContainerHelper::ReverseIterator ListContainerHelper::rend()
{
    return ReverseIterator(data_.get(), static_cast<size_t>(-1), NULL, size());
}

ListContainerHelper::ConstIterator ListContainerHelper::cbegin() const
{
    if (data_->IsEmpty())
        return cend();

    size_t id = data_->FirstInnerListId();
    return ConstIterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
}

ListContainerHelper::ConstIterator ListContainerHelper::cend() const
{
    if (data_->IsEmpty())
        return ConstIterator(data_.get(), 0, NULL, size());

    size_t id = data_->list_count();
    return ConstIterator(data_.get(), id, NULL, size());
}

ListContainerHelper::Iterator ListContainerHelper::begin()
{
    if (data_->IsEmpty())
        return end();

    size_t id = data_->FirstInnerListId();
    return Iterator(data_.get(), id, data_->InnerListById(id)->Begin(), 0);
}

ListContainerHelper::Iterator ListContainerHelper::end()
{
    if (data_->IsEmpty())
        return Iterator(data_.get(), 0, NULL, size());

    size_t id = data_->list_count();
    return Iterator(data_.get(), id, NULL, size());
}

ListContainerHelper::ConstIterator ListContainerHelper::IteratorAt(
    size_t index) const
{
    DCHECK_LT(index, size());
    size_t original_index = index;
    size_t list_index;
    for (list_index = 0; list_index < data_->list_count(); ++list_index) {
        size_t current_size = data_->InnerListById(list_index)->size;
        if (index < current_size)
            break;
        index -= current_size;
    }
    return ConstIterator(data_.get(), list_index,
        data_->InnerListById(list_index)->ElementAt(index),
        original_index);
}

ListContainerHelper::Iterator ListContainerHelper::IteratorAt(size_t index)
{
    DCHECK_LT(index, size());
    size_t original_index = index;
    size_t list_index;
    for (list_index = 0; list_index < data_->list_count(); ++list_index) {
        size_t current_size = data_->InnerListById(list_index)->size;
        if (index < current_size)
            break;
        index -= current_size;
    }
    return Iterator(data_.get(), list_index,
        data_->InnerListById(list_index)->ElementAt(index),
        original_index);
}

void* ListContainerHelper::Allocate(size_t size_of_actual_element_in_bytes)
{
    DCHECK_LE(size_of_actual_element_in_bytes, data_->element_size());
    return data_->Allocate();
}

size_t ListContainerHelper::size() const
{
    return data_->size();
}

bool ListContainerHelper::empty() const
{
    return data_->IsEmpty();
}

size_t ListContainerHelper::MaxSizeForDerivedClass() const
{
    return data_->element_size();
}

size_t ListContainerHelper::GetCapacityInBytes() const
{
    return data_->Capacity() * data_->element_size();
}

void ListContainerHelper::clear()
{
    data_->Clear();
}

size_t ListContainerHelper::AvailableSizeWithoutAnotherAllocationForTesting()
    const
{
    return data_->NumAvailableElementsInLastList();
}

// ListContainerHelper::Iterator
/////////////////////////////////////////////////
ListContainerHelper::Iterator::Iterator(CharAllocator* container,
    size_t vector_ind,
    char* item_iter,
    size_t index)
    : PositionInCharAllocator(container, vector_ind, item_iter)
    , index_(index)
{
}

ListContainerHelper::Iterator::~Iterator() { }

size_t ListContainerHelper::Iterator::index() const
{
    return index_;
}

// ListContainerHelper::ConstIterator
/////////////////////////////////////////////////
ListContainerHelper::ConstIterator::ConstIterator(
    const ListContainerHelper::Iterator& other)
    : PositionInCharAllocator(other)
    , index_(other.index())
{
}

ListContainerHelper::ConstIterator::ConstIterator(CharAllocator* container,
    size_t vector_ind,
    char* item_iter,
    size_t index)
    : PositionInCharAllocator(container, vector_ind, item_iter)
    , index_(index)
{
}

ListContainerHelper::ConstIterator::~ConstIterator() { }

size_t ListContainerHelper::ConstIterator::index() const
{
    return index_;
}

// ListContainerHelper::ReverseIterator
/////////////////////////////////////////////////
ListContainerHelper::ReverseIterator::ReverseIterator(CharAllocator* container,
    size_t vector_ind,
    char* item_iter,
    size_t index)
    : PositionInCharAllocator(container, vector_ind, item_iter)
    , index_(index)
{
}

ListContainerHelper::ReverseIterator::~ReverseIterator() { }

size_t ListContainerHelper::ReverseIterator::index() const
{
    return index_;
}

// ListContainerHelper::ConstReverseIterator
/////////////////////////////////////////////////
ListContainerHelper::ConstReverseIterator::ConstReverseIterator(
    const ListContainerHelper::ReverseIterator& other)
    : PositionInCharAllocator(other)
    , index_(other.index())
{
}

ListContainerHelper::ConstReverseIterator::ConstReverseIterator(
    CharAllocator* container,
    size_t vector_ind,
    char* item_iter,
    size_t index)
    : PositionInCharAllocator(container, vector_ind, item_iter)
    , index_(index)
{
}

ListContainerHelper::ConstReverseIterator::~ConstReverseIterator() { }

size_t ListContainerHelper::ConstReverseIterator::index() const
{
    return index_;
}

} // namespace cc
